Ghi chú NL (độ phức tạp)

Ghi chú NL (độ phức tạp)

↑ N. Immerman (1988). “Nondeterministic space is closed under complementation”. SIAM Journal on Computing. 17: 935–938.
↑ R. Szelepcsényi (1988). “The method of forced enumeration for nondeterministic automata”. Acta Informatica. Springer-Verlag New York, Inc. 26 (3): 279–284. doi:10.1007/BF00299636.

Tài liệu thao khảo

Papadimitriou, C. (1994). “Chapter 16: Logarithmic Space”. Computational Complexity. Addison-Wesley. ISBN 0-201-53082-1.
Michael Sipser (1997). “Sections 8.4–8.6: The Classes L and NL, NL-completeness, NL equals coNL”. Introduction to the Theory of Computation. PWS Publishing. tr. 294–302. ISBN 0-534-94728-X.
Introduction to Complexity Theory: Lecture 7. Oded Goldreich. Proposition 6.1. Goldreich gọi lớp C ở trên là badRSPACE(log n).

x t s Các lớp độ phức tạp quan trọng (thêm)
Các lớp được coi là giải được	DLOGTIME • AC0 • ACC0 • TC0 • L • SL • RL • NL • NC • SC • P (P-đầy đủ) • ZPP • RP • BPP • BQP
Các lớp có thể không giải được	UP • NP (NP-đầy đủ · NP-khó · co-NP · co-NP-đầy đủ) • AM • PH • PP • #P (#P-đầy đủ) • IP • PSPACE (PSPACE-đầy đủ)
Các lớp được coi là không giải được	EXPTIME • NEXPTIME • EXPSPACE • ELEMENTARY • PR • R • RE • ALL
Các hệ thống cấp bậc	Cấp bậc đa thức • Cấp bậc hàm mũ • Cấp bậc Grzegorczyk • Cấp bậc số học
Các nhóm các lớp độ phức tạp	DTIME • NTIME • DSPACE • NSPACE • Chứng minh có thể kiểm chứng ngẫu nhiên • Hệ thống chứng minh tương tác

Liên quan

NLE Choppa NL (độ phức tạp) NLP NLTT 39886 Nla.gov.au NLTK NLG NLUI NLH .nl

Tài liệu tham khảo

WikiPedia: NL (độ phức tạp) http://www.cs.umass.edu/~immerman/pub/space.ps http://www.wisdom.weizmann.ac.il/~oded/PS/CC/l7.ps //doi.org/10.1007%2FBF00299636 https://archive.org/details/introductiontoth00sips https://archive.org/details/introductiontoth00sips...